
/**
 * 买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 **某一天** 买入这只股票，并选择在 **未来的某一个不同的日子** 卖出该股票。
设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
输入：[7,1,5,3,6,4]
输出：5
 */
/**
 * dp[i][0|1] 第i天买(持有)｜卖股票（不持有）的最大利润 0-买入 1-卖出
 * 最终 dp[prices.length-1][1] 一定是卖出才会有收益，不然都是负债
 *
 * 【转移方程】
 * max(没有状态改变，改变->买入，卖出）
 * dp[i][0] = Math.max(dp[i-1][0], dp[i-1][0]-prices[i])  dp[i-1][0]-prices[i]持有的基础上买入今天的股票
 * dp[i][1] = Math.max(dp[i-1][1], prices[i]+dp[i][0])  prices[i]+dp[i][0] 卖出股票，当前价格-持有负债=收益
 *
 * 【初始化】dp[0]=[-prices[0], 0]
 */
var maxProfit = function(prices) {
  const m = prices.length;
  const dp = Array(m).fill([0,0]); //!注意初始化
  dp[0] = [-prices[0], 0]; //[has, no]
  for(let i=1; i<m;i++) {
    dp[i] = [
      Math.max(dp[i-1][0], -prices[i]), //只有一天买
      Math.max(dp[i-1][1], dp[i-1][0]+prices[i]) //只有一天卖
    ];
  }
  return dp[m-1][1];
}
const prices = [7,1,5,3,6,4];
console.log('买卖股票的最佳时机-动规',maxProfit(prices)); //5

/**
 * 优化成一维数组
 * 只有两个状态 dp[0]不操作， dp[1]持有， dp[2]不持有
 */
var maxProfit0 = function (prices) {
  const dp = Array(3).fill(0);
  dp[1] = -prices[0];
  for(let i = 1; i< prices.length; i++) {
    dp[1] = Math.max(dp[1], -prices[i]);
    dp[2] = Math.max(dp[2], dp[1]+prices[i]);
  }
  return dp[2];
  // const m = prices.length;
  // let has = -prices[0]
  // let profit = 0;
  // for(let i=0;i<m;i++) {
  //   has = Math.max(has, -prices[i])
  //   profit = Math.max(profit, has+prices[i])
  // }
  // return profit
}
console.log('买卖股票的最佳时机-动规0:',maxProfit0(prices)); //5

/**
 * 贪心
 * 找左侧的最小值、右侧最大值
 */
var maxProfit01 = function(prices) {
  let lowerPrice = prices[0];
  let profit = 0;
  for(let i=0;i<prices.length;i++) {
    lowerPrice = Math.min(lowerPrice, prices[i]);
    profit = Math.max(profit, prices[i]-lowerPrice)
  }
  return profit;
}
console.log('买卖股票的最佳时机-贪心',maxProfit01(prices)); //5